/*
    Copyright 2007-2008 Adrien Guillon.  All Rights Reserved.

    This file is part of TBB Community Code. 

    TBB Community Code is free software; you can redistribute it
    and/or modify it under the terms of the GNU General Public License
    version 2 as published by the Free Software Foundation.

    TBB Community Code is distributed in the hope that it will be
    useful, but WITHOUT ANY WARRANTY; without even the implied warranty
    of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with TBB Community Code; if not, write to the Free Software
    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    As a special exception, you may use this file as part of a free software
    library without restriction.  Specifically, if other files instantiate
    templates or use macros or inline functions from this file, or you compile
    this file and link it with other files to produce an executable, this
    file does not by itself cause the resulting executable to be covered by
    the GNU General Public License.  This exception does not however
    invalidate any other reasons why the executable file might be covered by
    the GNU General Public License.
*/

#include "tbb/task_scheduler_init.h"
#include "tbb/concurrent_vector.h"
#include "tbb/partitioner.h"


#include "parallel_for_group.h"
#include "separator.h"
#include "grouped_range.h"
#include "ungrouped_range.h"

#include <iostream>

#include <deque>

/**
 * Simple implementation of Conway's Game of Life.
 * Note that this is an illustration of the use of parallel_for_group, and
 * is not very efficient.  Just an example usage.
 * Also, note that the edges of the boards are not handled.
 */

/**
 * A simple representation of a coordinate.
 */
struct Coord
{
    Coord(int x, int y) { this->x = x; this->y = y; }
    int x;
    int y;
};


/**
 * A representation of the Game of Life playing board, which
 * contains all the cells.  The cells are part of the board, and
 * so must be manipulated from this class.
 */
class GameBoard
{
public:
    GameBoard(const int height, const int width) : _height(height), _width(width)
    {
        _gameBoard.insert(_gameBoard.begin(), height*width, false);
    }

    /**
     * Determine if a cell is alive at the provided coordinate.
     */
    bool isCellAlive(const Coord& v)
    {
        return _gameBoard[translateCoord(v)];
    }

    bool isCellAlive(const Coord& v) const
    {
        return _gameBoard[translateCoord(v)];
    }

    int numberCellsAlive()
    {
        int tally = 0;

        for(int x = 0; x < _width; ++x)
        {
            for(int y = 0; y < _height; ++y)
            {
                if(isCellAlive(Coord(x,y)))
                    tally++;
            }
        }

        return tally;

    }

    /**
     * Toggle the life of a cell at the provided coordinate.
     */
    void toggleLife(const Coord& v)
    {
        boardType::size_type coord = translateCoord(v);
        _gameBoard[coord] = !_gameBoard[coord];
    }

    void setAlive(const Coord& v)
    {
        _gameBoard[translateCoord(v)] = true;
    }

    void setDead(const Coord& v)
    {
        _gameBoard[translateCoord(v)] = false;
    }

    void setLife(const Coord& v, bool state)
    {
        _gameBoard[translateCoord(v)] = state;
    }

    int height() { return _height; }
    int height() const { return _height; }

    int width() { return _width; }
    int width() const { return _width; }

private:
    typedef std::deque<bool> boardType; 

    /**
     * Translate a coordinate to an actual offset within the vector.
     * NOTE: The board is stored as a concatenation of (row) number of
     * (width)-elements.
     */
    const boardType::size_type translateCoord(const Coord& v)
    {
        return (v.y * _width) + v.x;
    }

    const boardType::size_type translateCoord(const Coord& v) const
    {
        return (v.y * _width) + v.x;
    }

    boardType _gameBoard;

    boardType::size_type _height, _width;

};


/**
 * A LocalGameBoard is basically the same as a GameBoard, the only
 * difference is that it stores the coordinate of its center on the original
 * game board.  So for a 3x3 LocalGameBoard the center is (1,1), but on the
 * original gameboard it might have been (10, 14).
 *
 * Use getOriginalCoord() to get the original game board location.
 */
class LocalGameBoard : public GameBoard
{
public:
    LocalGameBoard(const Coord& v, int height, int width) : GameBoard(height, width), _originalCoord(v) { }
    Coord getOriginalCoord() { return _originalCoord; }

private:
    Coord _originalCoord;

};




/**
 * Print a board to the screen.
 */
void printBoard(const GameBoard& board)
{
    int height = board.height();
    int width = board.width();
    bool state;

    std::cout << "<START BOARD>" << std::endl;
    for(int y = 0; y < height; ++y)
    {
        for(int x = 0; x < width; ++x)
        {
            state = board.isCellAlive(Coord(x,y));

            if(state)
                std::cout << 'X';
            else
                std::cout << '_';
        }
        std::cout << '\n';
    }
    std::cout << "<END BOARD>" << std::endl;
}


/**
 * Define a separator for tcc::parallel_for_group which will separate the game
 * board into segments which can be processed independently without accessing
 * the main game board.  Each group will consist of 9 coordinates, which
 * represents a single cell and its surroundings.
 */
class gameboard_separator : public tcc::separator<GameBoard, LocalGameBoard>
{
public:
    separation_type separate(const GameBoard& board) const
    {
        
        // Create a collection of groups which will be returned and used
        // for processing.
        separation_type result;

        // We'll need board width/height frequently, so save them

        int width = board.width();
        int height = board.height();


        // Each group will consist of at most 9 items, the cell of interest and its
        // touching cells.
        // Cells which are on the edges of the board are handled in a special manner,
        // basically anywhere off the board is considered to be unoccupied.
        
        // Inner board first
        for(int y = 1; y < height - 1; ++y)
        {
            for(int x = 1; x < width - 1; ++x)
            {
                // Construct and populate a new game board
                LocalGameBoard cellBoard(Coord(x,y), 3,3);
                
                for(int row = -1; row < 2; ++row)
                {
                    for(int col = -1; col < 2; ++col)
                    {
                        cellBoard.setLife(Coord(col+1, row+1), board.isCellAlive(Coord(x + col, y + row)));
                    }
                }

                result.grouped.push_back(cellBoard);
            }
        }
        return result;

    }
};



class ApplyCellLogic
{
public:

    void operator()(gameboard_separator::grouped_range_type& range) const
    {
        typedef gameboard_separator::grouped_container_type::iterator grouped_iterator;
        
        // Execute actual cell logic
        for(grouped_iterator i = range.begin(); i != range.end(); ++i)
        {
            // Is the cell alive?
            if(i->isCellAlive(Coord(1,1)))
            {
                // Cell Alive

                // Are there 2 or 3 neighbors?
                // Subtract one because we are alive and our own neighbor
                int neighborCount = i->numberCellsAlive() - 1;
                if(neighborCount < 2 || neighborCount > 3)
                {
                    i->setDead(Coord(1,1));
                }

            }
            else
            {
                // Cell Dead

                // Are there exactly three neighbors?
                if(i->numberCellsAlive() == 3)
                {
                    i->setAlive(Coord(1,1));
                }
            }

        }

    }

    void operator()(gameboard_separator::ungrouped_range_type& range) const
    {
    }

};


/**
 * Take a separation of the game board and stitch them back together
 * into a full gameboard again.
 */
void recombineGameBoardSeparation(GameBoard& x, gameboard_separator::separation_type& separation)
{
    gameboard_separator::grouped_iterator grouped_end = separation.grouped.end();
    for(gameboard_separator::grouped_iterator i = separation.grouped.begin(); i != grouped_end; ++i)
    {
        x.setLife(i->getOriginalCoord(), i->isCellAlive(Coord(1,1)));
    }
}


/**
 * An implementation of Conway's game of life, which utilizes parallel_for_group
 * for parallel computation.
 */

int main()
{

    // Universe constants, the height and width must
    // each be mutliples of 3 to simplify the game.
    const int universeWidth = 33;
    const int universeHeight = 33;

    // As always, initialize the TBB scheduler
    tbb::task_scheduler_init init;

    // Initialize the game board
    GameBoard board(universeHeight, universeWidth);

    // Read in the game board from stdin.
    // The game board should consist of X and _ characters,
    // where X indicates a living cell, and _ indicates an unoccupied space.

    char cellState;
    for(int y = 0; y < universeHeight; ++y)
    {
        for(int x = 0; x < universeWidth; ++x)
        {
            std::cin >> cellState;

            if(cellState == 'X')
                board.setAlive(Coord(x,y));
            else if (cellState == '_')
                board.setDead(Coord(x,y));
            else
                return 1;
        }
    }

    gameboard_separator::separation_type resultingBoard;
    for(int i = 0; i < 100; ++i)
    {
        //std::cout << "Board at time: " << i << std::endl;
        //printBoard(board);
        resultingBoard = tcc::parallel_for_group(board, gameboard_separator(), ApplyCellLogic(), tbb::auto_partitioner());
        recombineGameBoardSeparation(board, resultingBoard);
    }


    return 0;
}



